package NC60_判断一棵二叉树是否为搜索二叉树和完全二叉树;

import java.util.*;

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
}

public class Solution {
    /**
     *
     * @param root TreeNode类 the root
     * @return bool布尔型一维数组
     */
    public boolean[] judgeIt (TreeNode root) {
        // write code here
        boolean[] res = new boolean[2];
        res[0] = isSearchTreeBST(root);
        res[1] = isAllTreesBST(root);
        
        return res;
    }

    private boolean isAllTreesBST(TreeNode root) {
        if (root == null){
            return true;
        }
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        TreeNode left = null;
        TreeNode right = null;
        boolean flag = false;   // 标记是否遇到节点不双全的节点

        while (!queue.isEmpty()){
            root = queue.poll();
            left = root.left;
            right = root.right;

            if ((flag && !(left == null && right == null)) || (left == null && right != null)){
                return false;
            }

            if (left != null){
                queue.offer(left);
            }
            if (right != null){
                queue.offer(right);
            }

            if (left == null || right == null){
                flag = true;
            }
        }
        return true;
    }

    long pre = Integer.MIN_VALUE;
    private boolean isSearchTreeBST(TreeNode root) {
        if (root == null){
            return true;
        }

        if (!isSearchTreeBST(root.left)){
            return false;
        }

        // 访问当前节点：
        // 如果当前节点小于等于中序遍历的前一个节点，说明不满足BST，返回false
        if (root.val <= pre){
            return false;
        }
        pre = root.val;

        return isSearchTreeBST(root.right);
    }
}